package com.algorithm.ch1.cjm.dynamic;

/**
 * 钢条切割
 * 长度为i英寸的钢条的价格为p(i)(i = 1,2, ...,)
 * 长度i      1   2   3   4   5   6   ... 10
 * 价格p(i)   1   5   8   9   10  17  ... 30
 *
 * 问题：给定一段长度为n 英寸的钢条和一个价格表，求切割钢条方案，使得销售收益R(n)最大
 * 注意：如果长度为n 英寸会获得最大收益，我们当然可以选择不做任何切割。
 *
 *
 * 钢条切割问题满足 最优子结构 性质：问题的最优解由相关子问题的最优解组合而成，而这些
 * 子问题可以独立求解
 */
public class CutSteel {

    public static void main(String[] args) {

    }

    /**
     * 递归法求解
     * 把长度为n的钢条,分隔为不需要切割的长度i, 这部分的最大收益为p(i), 和需要切割的长度n -i。
     * r(n) = max(p(i) + r(n-i))   (1<= i <=n)
     *
     * 每一层都有最优解的选择
     * @return
     */
    public static int cut(int[] p, int n){

        if(n == 0 || p == null || p.length == 0) {
            return 0;
        }

        int max = 0;

        for (int i = 1; i <= n; i++) {

            max = Math.max(max, p[i] + cut(p, n - i));
        }

        return max;
    }

    /**
     * 备忘录法则
     * 把重复计算的结果记录下来，避免大量重复计算
     * @param p
     * @param n
     * @return
     */
    public static int cutMemo(int[] p, int n){

        if(n == 0 || p == null || p.length == 0) {
            return 0;
        }

        //备忘录法则,记录每个小单位的最优解
        int[] res = new int[n + 1];

        int index = 0;
        while (index++ <= n){
            res[index] = -1;
        }

        return getCutRes(res, p, n);
    }

    //获取结果
    private static int getCutRes(int[] res, int[] p , int n){

        if(res[n] != -1) {
            return res[n];
        }

        int max = 0;
        for (int i = 1; i <= n; i++) {

            max = Math.max(max, p[i] + getCutRes(res, p, n -i));
        }

        res[n] = max;

        return res[n];
    }

    /**
     * 自底向上的动态规划
     * @param p
     * @return
     */
    public static int buttomUpCut(int[] p, int n){

        int[] res = new int[n + 1];

        for (int i = 1; i <= n; i++) {

            int max = -1;

            for (int j = 1; j <= i; j++) {
                max = Math.max(max, p[i] + res[i - j]);
            }
            res[i]  = max;
        }

        return res[n];
    }

}
